39. 组合总和

Similar Question

Solution Tips

方案一: 回溯 - N 叉树思路

var combinationSum = function(candidates, target) {
    const res = [];
    const cur = [];
    let curSum = 0;
    candidates.sort((a, b) => a - b);

    function backTracking(curIndex) {
        if (curSum === target) {
            res.push([...cur])
            return;
        }

        // 剪枝, 可以考虑升序排序然后剪枝
        for (let i = curIndex; i < candidates.length; i++) {
            cur.push(candidates[i]);
            curSum += candidates[i];

            if (curSum > target) {
                // 提前结束
                cur.pop();
                curSum -= candidates[i];
                return;
            }

            backTracking(i);
            // 回溯操作
            cur.pop();
            curSum -= candidates[i];
        }
    }

    backTracking(0);
    return res;
};

方案二: 回溯 - 二元思路

var combinationSum = function(candidates, target) {
    const ans = [];
    const dfs = (target, combine, idx) => {
        if (idx === candidates.length) {
            return;
        }
        if (target === 0) {
            ans.push(combine);
            return;
        }
        // 直接跳过
        dfs(target, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
        }
    }

    dfs(target, [], 0);
    return ans;
};